package com.gxc.fibonacci;

/**
 * 字符串只由0和1两种字符构成，
 * 当字符串长度为1时，所有可能的字符串为"0"、"1";
 * 当字符串长度为2时，所有可能的字符串为"00"、"01"、"10"、"11";
 * 当字符串长度为3时，所有可能的字符串为"000"、"001"、"010"、"011"、"100","110"、"111","101"、
 * 如果某一个字符串中，只要是出现'0的位置，左边就靠着'1'，这样的字符串叫作达标字符串。
 * 给定一个正数N，返回所有长度为N的字符串中，达标字符串的数量。
 * 比如，N=3，返回3，因为只有"101"、"110”、"111"达标。
 *
 * 当字符串长度为1时，达标字符串 "1";  1
 * 当字符串长度为2时，达标字符串 "10"、"11";  2
 * 当字符串长度为3时，达标字符串 "110"、"111","101"、  3
 * 当字符串长度为4时，达标字符串 1111 1110 1101 1011 1010   5
 *
 * 斐波那契数列
 * 1 1 2 3 5 8 ....
 *
 * 题目转为求n+1的位置的斐波那契数列
 * 斐波那契数列矩阵推导
 * https://blog.csdn.net/lanchunhui/article/details/80953084
 *
 */
public class TargetString {

    public static void main(String[] args) {
        int N = 3;
        System.out.println(fi(N+1));
    }

    public static int fi(int n) {
        if (n < 1) return 0;

        if (n == 1 || n ==2) return 1;
        //基础矩阵
        int[][] base = new int[][]{{1, 1},
                                   {1, 0}};
        //f(n+2)=f(n)+f(n+1)
        int[][] result = matrixPower2(base, n-2);
        return result[0][0] + result[1][0];
    }

    /**
     * 矩阵的i次方
     * @param base
     * @param i
     * @return
     */
    private static int[][] matrixPower(int[][] base, int i) {
        int[][] result = new int[base.length][base[0].length];
        for (int j = 0; j < result.length; j++) {
            result[j][j] = 1;
        }

        for (int j = 0; j < i; j++) {
            result = multiMatrix(result, base);
        }
        
        return result;
    }

    /**
     * 矩阵的i次方--加速
     * @param base
     * @param p
     * @return
     */
    private static int[][] matrixPower2(int[][] base, int p) {
        int[][] result = new int[base.length][base[0].length];
        //单位矩阵
        for (int j = 0; j < result.length; j++) {
            result[j][j] = 1;
        }

        int[][] t = base;
        for (; p!=0; p>>=1) {
            if ((p & 1) != 0) {
                result = multiMatrix(result, t);
            }
            t = multiMatrix(t, t);
        }

        return result;
    }

    /**
     * 矩阵相乘
     * @param m
     * @param n
     * @return
     */
    private static int[][] multiMatrix(int[][] m, int[][] n) {
        int[][] result = new int[m.length][n[0].length];

        int row = result.length;
        int col = result[0].length;

        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                for (int k = 0; k < n.length; k++) {
                    result[i][j] += m[i][k] * n[k][j];
                }
            }
        }
        return result;
    }

}
